package com.lfg.leetcode.leetcode500;


import com.alibaba.fastjson.JSON;

public class No918maxSubarraySumCircular {
    public static void main(String[] args) {
//        System.out.println(JSON.toJSONString(maxSubarraySumCircular(new int[]{1, -2, 3, -2})));
        System.out.println(JSON.toJSONString(maxSubarraySumCircular(new int[]{5, -3, 5})));
    }

    public static int maxSubarraySumCircular(int[] nums) {

        int ret = 0;
        int cnt = 0;
        for (int num : nums) {
            cnt += num;
            ret = Math.max(ret, cnt);
        }

        int[] right = new int[nums.length];
        int[] rightMax = new int[nums.length];
        right[nums.length-1] = nums[nums.length-1];
        rightMax[nums.length-1] = nums[nums.length-1];
        for (int i = nums.length - 2; i > -1; i--) {
            right[i] =right[i+1] + nums[i];
            rightMax[i] = Math.max(right[i], rightMax[i+1]);
        }
        int left = 0;

        for (int i = 0; i <nums.length-2; i++) {
            left += nums[i];
            ret = Math.max(ret, left + rightMax[i+2]);
        }


        return ret;
    }
}



